package class04_归并排序.test;

/**
 * 最小和问题
 */
public class Code02_SmallSum {
    public static int smallSum(int[] arr){
        if(arr == null || arr.length < 2){
            return 0;
        }
        return process(arr,0,arr.length - 1);
    }

    private static int process(int[] arr, int L, int R) {
        if(L == R){
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        return
            process(arr, L, mid)
         +  process(arr,mid + 1, R)
         +  merge(arr, L, mid, R);
    }

    private static int merge(int[] arr, int L, int mid, int R) {
        int[] help = new int[R - L + 1];
        int l = L;
        int r = mid + 1;
        int index = 0;
        int mixSum = 0;
        while(l <= mid && r <= R){
            if(arr[l] < arr[r]){
                mixSum += (arr[l] * (R - r + 1));
            }
//            mixSum += arr[l] < arr[r] ? (R - r + 1) * arr[l] : 0; R-(mix+1)+1

            help[index++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
        }
        while (l <= mid){
            help[index++ ] = arr[l++];
        }
        while (r <= R){
            help[index++ ] = arr[r++];
        }
        for (int i = 0; i < help.length; i++) {
            arr[i + L] = help[i];
        }
        return mixSum;
    }

    public static void main(String[] args) {
        int testTime = 5000000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize,maxValue);
            int[] arr2 = copyArray(arr1);
            if(smallSum(arr1) != comparator(arr2)){
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }

    private static void printArray(int[] arr1) {
        if(arr1 != null){
            for (int i = 0; i < arr1.length; i++) {
                System.out.print(arr1[i] + " ");
            }
            System.out.println();
        }
    }

    private static int comparator(int[] arr) {
        if(arr == null || arr.length < 2){
            return 0;
        }
        int mixSum = 0;
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 0 ; j < i; j++) {
                if(arr[i] > arr[j]){
                    mixSum+=arr[j];
                }
            }
        }
        return mixSum;
    }

    private static int[] copyArray(int[] arr) {
        if(arr == null){
            return new int[0];
        }
        int[] arr2 = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arr2[i] = arr[i];
        }
        return arr2;
    }

    private static int[] generateRandomArray(int maxSize, int maxValue) {
        int size = (int)(Math.random() * (maxSize + 1));
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = (int)(Math.random() * (maxValue + 1));
        }
        return arr;
    }
}
